#include "test_coll.h"
#include <cstdlib>
#include <iostream>
#include <ctime>

class TLineSegment1
{
public:
	static int is_line;
	TLineSegment1()
	{};
	TPlaneVect org;
	TPlaneVect shift;
	void Refine()
	{
		if ((shift.x < 0) || ((shift.x == 0) && (shift.y < 0)))
		{
			org = org + shift;
			shift = -shift;
		}
	};
	void Init(TLineSegment1 &s)
	{
		org = s.org;
		shift = s.shift;
	};
	void InitRandom(CRandomValueGen &rv, int seg_n, int type)
	{
		if (type == debug)
		{
			org.x = rv.GetRandomDouble();
			org.y = rv.GetRandomDouble();
			shift.x = rv.GetRandomDouble() - org.x;
			shift.y = rv.GetRandomDouble() - org.y;
			Refine();
		}
		else //type == random
		{
			org.x = std::rand() - RAND_MAX;
			org.y = std::rand() - RAND_MAX;
			shift.x = std::rand() - RAND_MAX - org.x;
			shift.y = std::rand() - RAND_MAX - org.y;
			Refine();
		}

	};

	TPlaneVect BegPoint()
	{
		return org;
	};
	TPlaneVect EndPoint()
	{
		return org + shift;
	};
	void BegPoint(double &x, double &y)
	{
		x = org.x;
		y = org.y;
	};
	void EndPoint(double &x, double &y)
	{
		x = org.x + shift.x;
		y = org.y + shift.y;
	};
	int under(TPlaneVect &v) //segment placed under point v
	{
		double res = (v - org) % shift;
		return (res <= 0);
	};
	int upper(TPlaneVect &v) 
	{
		double res = (v - org) % shift;
		return (res > 0);
	};
	double YAtX(double X)
	{
		return org.y + shift.y * (X - org.x) / shift.x;
	};
	friend int below(double X, TLineSegment1 *s1, TLineSegment1 *s2);
	friend int IntPoint(TLineSegment1 *s1, TLineSegment1 *s2, TPlaneVect *p);
	friend int StripePoint(double b, double e, TLineSegment1 *s1, TLineSegment1 *s2, TPlaneVect *p);
	//for optimal alg only
	friend int IntInside(double b, double e, TLineSegment1 *s1, TLineSegment1 *s2);
};

int TLineSegment1::is_line = 1;

int below(double X, TLineSegment1* s1, TLineSegment1* s2)
{ 
	if (s1 == s2)
		return 0;
	double dx1 = s1->shift.x, dx2 = s2->shift.x;
	double dy1 = s1->shift.y, dy2 = s2->shift.y;
	double y1, y2;
	if ((dx1 == 0.0) || (s1->org.x + dx1 == X))
	{
		double res = (s1->org + s1->shift - s2->org) % s2->shift;
		if (fabs(res) == 0.0)
			throw 1;
		return (res > 0);
	}
	if (s2->org.x + dx2 == X)
	{
		double res = (s2->org + s2->shift - s1->org) % s1->shift;
		if (fabs(res) == 0.0)
			throw 1;
		return (res < 0);
	}
	y1 = (s1->org.y * dx1 + (X - s1->org.x) * dy1) * dx2;
	y2 = (s2->org.y * dx2 + (X - s2->org.x) * dy2) * dx1;
	return y1 < y2;
}


int IntPoint(TLineSegment1* s1, TLineSegment1* s2, TPlaneVect *p)
{ 
	double b1 = max(s1->org.x, s2->org.x);
	double b2 = min(s1->org.x + s1->shift.x, s2->org.x + s2->shift.x);
	if (b1 >= b2)
		return 0;
	TPlaneVect delt = s2->org - s1->org;
	double prod = s1->shift % s2->shift, mul;
	if (((mul = s1->shift % delt) > 0) ^ (mul + prod > 0))
		if (((mul = delt % s2->shift) > 0) ^ (mul - prod > 0))
		{
			if (prod == 0)
				return 0;
			if (p)
				*p = s1->org + ((double)fabs(mul / prod)) * s1->shift;
			return 1;
		}
		return 0;
} 

int StripePoint(double b, double e, TLineSegment1* s1, TLineSegment1* s2, TPlaneVect *p)
{ 
	TPlaneVect delt = s2->org - s1->org;
	double prod = s1->shift % s2->shift, mul, xc;
	if (((mul = s1->shift % delt) > 0) ^ (mul + prod > 0))
	{
		if (prod == 0)
			return 0;
		mul = mul / prod;
		xc = s2->org.x - mul * s2->shift.x;
		if ((xc <= b) || (xc > e))
			return 0;
		if (p)
		{
			p->x = xc;
			p->y = s2->org.y - mul * s2->shift.y;
		}
		return 1;
	}
	return 0;
}

int IntInside(double b, double e, TLineSegment1* s1, TLineSegment1* s2)
{ 
	TPlaneVect delt = s2->org-s1->org;
	double prod = s1->shift % s2->shift, mul = s1->shift % delt, xc;
	if ((mul > 0) ^ (mul + prod > 0))
	{
		if (prod == 0)
			return 0;
		mul = mul / prod;
		xc = s2->org.x - mul * s2->shift.x;
		if ((xc <= b) || (xc > e))
			return 0;
		return 1;
	}
	return 0;
}

class TLineSegment2
{
public:
	static int is_line;
	double x1, x2, a, b;
	TLineSegment2()
	{
		x1 = 0;
		x2 = 0;
		a = 0;
		b = 0;
	};
	void Init(TLineSegment1 &s)
	{
		x1 = s.org.x;
		x2 = s.org.x + s.shift.x;
		a = s.shift.y / s.shift.x;
		b = s.org.y - a * s.org.x;
	};
	void InitRandom(CRandomValueGen &rv, int s_n, int type)
	{
		TLineSegment1 seg;
		seg.InitRandom(rv, s_n, type);
		Init(seg);
	};

	TPlaneVect BegPoint()
	{
		return TPlaneVect(x1, a * x1 + b);
	};
	TPlaneVect EndPoint()
	{
		return TPlaneVect(x2, a * x2 + b);
	};
	void BegPoint(double &x, double &y)
	{
		x = x1;
		y = a * x1 + b;
	};
	void EndPoint(double &x, double &y)
	{
		x = x2;
		y = a * x2 + b;
	};
	int under(TPlaneVect &v)
	{
		return v.y >= (v.x * a + b);
	};
	int upper(TPlaneVect &v) 
	{
		return v.y < (v.x * a + b);
	};
	double YAtX(double X)
	{
		return a * X + b;
	};
	friend int below(double X, TLineSegment2 *s1, TLineSegment2 *s2);
	friend int IntPoint(TLineSegment2 *s1, TLineSegment2 *s2, TPlaneVect *p);
	friend int StripePoint(double b, double e, TLineSegment2 *s1, TLineSegment2 *s2, TPlaneVect *p);
	//for optimal alg only
	friend int IntInside(double b, double e, TLineSegment2 *s1, TLineSegment2 *s2);
};

int TLineSegment2::is_line=1;

int below(double X, TLineSegment2* s1, TLineSegment2* s2)
{ 
	return (s1 != s2) && ((X * s1->a + s1->b) < (X * s2->a + s2->b));
}

int IntPoint(TLineSegment2* s1, TLineSegment2* s2, TPlaneVect *p)
{ 
	double x1 = max(s1->x1, s2->x1);
	double x2 = min(s1->x2, s2->x2);
	if (x1 >= x2)
		return 0;
	double da = s1->a - s2->a;
	if (da == 0)
		return 0;
	if (p)
	{
		p->x = (s2->b - s1->b) / da;
		if ((p->x >= x1) && (p->x <= x2))
		{
			p->y = p->x * s1->a + s1->b;
			return 1;
		}
	}
	else
	{
		double x = (s2->b - s1->b) / da;
		return ((x >= x1) && (x <= x2));
	} 
	return 0;
} 

int StripePoint(double b, double e, TLineSegment2* s1, TLineSegment2* s2, TPlaneVect *p)
{ 
	double x1 = max(s1->x1, s2->x1);
	double x2 = min(s1->x2, s2->x2);
	x1 = max(x1, b);
	x2 = min(x2, e);
	double da = s1->a - s2->a;
	if (da == 0)
		return 0;
	if (p)
	{
		p->x = (s2->b - s1->b) / da;
		if ((p->x >= x1) && (p->x <= x2))
		{
			p->y = p->x * s1->a + s1->b;
			return 1;
		}
	}
	else
	{
		double x = (s2->b - s1->b) / da;
		return ((x >= x1) && (x <= x2));
	} 
	return 0;
}

int IntInside(double b, double e, TLineSegment2 *s1, TLineSegment2 *s2)
{ 
	double x1 = max(s1->x1, s2->x1);
	double x2 = min(s1->x2, s2->x2);
	x1 = max(x1, b);
	x2 = min(x2, e);
	double da = s1->a - s2->a;
	if (da == 0)
		return 0;
	double x = (s2->b - s1->b) / da;
	if ((x >= x1) && (x <= x2))
		return 1;
	return 0;
}

PSeg first_segment_ptr=NULL;
template <class SEGMENT>
class SegmentFunctions
{
public:
	static void register_intersection(PRegObj r, PSeg s1, PSeg s2, int nInt, TPlaneVect *points)
	{
		(*(double *)r) += nInt;
	};

	static double __YAtX(PSeg s, double X)
	{
		return ((SEGMENT *)s)->YAtX(X);
	};

	static int __Below(double x, PSeg s1, PSeg s2)
	{
		return below(x, (SEGMENT*)s1, (SEGMENT*)s2);
	};
	static int __FindAndRegIPoints(PSeg s1, PSeg s2, PRegObj intersection_registrator, BOOL no_ip)
	{
		TPlaneVect P[2];
		TPlaneVect *p = no_ip ? NULL : P;
		int n = IntPoint((SEGMENT*)s1, (SEGMENT*)s2, p);
		if (n)
			register_intersection(intersection_registrator, s1, s2, n, p);
		return n; 
	};

	static int __FindAndRegIPointsInStripe(double b, double e, PSeg s1, PSeg s2, PRegObj intersection_registrator, BOOL no_ip)
	{
		TPlaneVect P[2];
		TPlaneVect *p = no_ip ? NULL : P;
		int n = StripePoint(b, e, (SEGMENT*)s1, (SEGMENT*)s2, p);
		if (n)
			register_intersection(intersection_registrator, s1, s2, n, p);
		return n; 
	};
	static void __BegPoint(PSeg s, double &x, double &y)
	{
		((SEGMENT*)s)->BegPoint(x, y);
	};
	static void __EndPoint(PSeg s, double &x, double &y)
	{
		((SEGMENT*)s)->EndPoint(x, y);
	};
	static int __Under(PSeg s1, PSeg s2)
	{
		return ((SEGMENT*)s1)->under(((SEGMENT*)s2)->BegPoint());
	};
	static int __IntInside(double b, double e, PSeg s1, PSeg s2)
	{
		return IntInside(b, e, (SEGMENT*)s1, (SEGMENT*)s2);
	}; 

};

PSeg* create_test_collection(int n, int distr)
{
	PSeg *colls = NULL;
	CRandomValueGen random_gen;
	int i;
	colls = new PSeg[n];
	TLineSegment2 *Colls = new TLineSegment2[n];
	for (i = 0; i < n; i++)
		colls[i] = Colls + i;
	if (distr == random)
		std::srand(std::time(0));
	for (i = 0; i < n; i++)
		Colls[i].InitRandom(random_gen, i, distr);
	first_segment_ptr = colls[0];
	return colls; 
};

void delete_test_collection(PSeg *colls)
{
	delete[] (TLineSegment2 *)colls[0];
	delete[] colls; 
};

double find_intersections(int SN, PSeg *colls, double *counters)
{
	if (colls == NULL)
		return 0;
	double int_numb = 0;
	CIntersectionFinder intersection_finder;
	double int_numb1 = 0;
	BOOL is_line;
	intersection_finder.set_segm_fuctions(
		SegmentFunctions<TLineSegment2>::__Below, 
		SegmentFunctions<TLineSegment2>::__FindAndRegIPoints, 
		SegmentFunctions<TLineSegment2>::__FindAndRegIPointsInStripe, 
		SegmentFunctions<TLineSegment2>::__BegPoint, 
		SegmentFunctions<TLineSegment2>::__EndPoint, 
		SegmentFunctions<TLineSegment2>::__Under, 
		SegmentFunctions<TLineSegment2>::__YAtX, 
		SegmentFunctions<TLineSegment2>::register_intersection, 
		&int_numb, 
		is_line = TLineSegment2::is_line
	);
	intersection_finder.dont_need_int_points = TRUE;
	intersection_finder.balaban_no_ip(SN, colls);
	memcpy(counters, intersection_finder.my_counter, sizeof(intersection_finder.my_counter));
	return int_numb + int_numb1;
};